


//接雨水
// 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
//算法一:
// 可以用动态规划来解决这个问题，首先，我们要知道，如果我们把柱子排成一列，那么每个柱子的高度就是它们之间的差值，
// 如果我们把柱子排成一行，那么每个柱子的高度就是它们之间的差值，这样，我们就可以用动态规划来解决这个问题了。


// /**
//  * @param {number[]} height
//  * @return {number}
//  */
 var trap = function(height) {
    let n=height.length;
    if(n===0) return 0;
    let res=0;

    let left_max=[] ,right_max=[];
    //记录左边数组的最大值
    left_max[0]=height[0];
    for(let i=1;i<n;i++){
      left_max[i]=Math.max(left_max[i-1],height[i]);
    }
    //记录右边数组的最大值
    right_max[n-1]=height[n-1];
    for(let i=n-2;i>=0;i--){
      right_max[i]=Math.max(right_max[i+1],height[i]);
    }
    //统计每一列的面积之和
    for(let i=0;i<n;i++){
      res+=Math.min(left_max[i],right_max[i])-height[i];
    }
    return res;
  };



// 我们注意到，解法二中。对于每一列，我们求它左边最高的墙和右边最高的墙，都是重新遍历一遍所有高度，这里我们可以优化一下。
// 首先用两个数组，max_left [i] 代表第 i 列左边最高的墙的高度，max_right[i] 代表第 i 列右边最高的墙的高度。（一定要注意下，第 i 列左（右）边最高的墙，是不包括自身的，和 leetcode 上边的讲的有些不同）
// 对于 max_left我们其实可以这样求。
// max_left [i] = Max(max_left [i-1],height[i-1])。它前边的墙的左边的最高高度和它前边的墙的高度选一个较大的，就是当前列左边最高的墙了。
// 对于 max_right我们可以这样求。
// max_right[i] = Max(max_right[i+1],height[i+1]) 。它后边的墙的右边的最高高度和它后边的墙的高度选一个较大的，就是当前列右边最高的墙了。
// 这样，我们再利用解法二的算法，就不用在 for 循环里每次重新遍历一次求 max_left 和 max_right 了。



console.log(trap([0,1,0,2,1,0,1,3,2,1,2,1]));